package 程序员面试金典;

import java.util.*;

public class MedianFinder {

    List<Integer> list;
    public MedianFinder() {
        list = new ArrayList<>();
    }

    public void addNum(int num) {
        if (list.isEmpty()) {
            list.add(num);
            return;
        }
        list.add(binarySearch(num), num);
    }

    private int binarySearch(int target) {
        int left = 0;
        int right = list.size();
        while (left < right) {
            int mid = (left + right) >>> 1;
            int key = list.get(mid);
            if (target >= key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public double findMedian() {
        int index = list.size() / 2;
        if (list.size() % 2 == 0) {
            return (list.get(index) + list.get(index - 1)) * 0.5;
        }
        return list.get(index);
    }
}
